﻿// 0911train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间
times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点，
wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？
如果不能使所有节点收到信号，返回 -1 

示例1
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
 */
class Solution01 {
public:
    struct Node
    {
        int index, val;
        Node(int index, int val) :index(index), val(val) {};

        bool operator<(const Node&other)const
        {
            return val > other.val;
        }
    };
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        //建表，保存下一个节点
		for (auto&node_vec:times)
		{
            //(ui, vi, wi) vi目标节点，wi时间
            int curr_i = node_vec[0];
            int next_i = node_vec[1];
            int next_val = node_vec[2];

            Node node(next_i, next_val);
            linked_map[curr_i].push_back(node);
		}

        //建表，保存每个数字的最小时间
        for (int i=1; i<=n; i++)
        {
            cost_map[i] = INT_MAX;
        }
        cost_map[k] = 0;//起点开销为0

        //优先队列 重载操作符 每次pop最小的元素
        priority_queue<Node>bfs_queue;
        //起点先进
        Node first_node(k, 0);
        bfs_queue.push(first_node);

        while (!bfs_queue.empty())
        {
            Node top_node = bfs_queue.top();
            bfs_queue.pop();

            //如果当前节点的值并非最小，直接跳过，不走这个路径
            if (top_node.val>cost_map.at(top_node.index))
            {
                continue;
            }

            if (linked_map.count(top_node.index)>0)
            {
                vector<Node>child_v = linked_map.at(top_node.index);
                for (auto&next_node:child_v)
                {
                    int next_min_val = cost_map[next_node.index];
                    if (next_min_val==INT_MAX || top_node.val+next_node.val<next_min_val)
                    {
                        int next_val = top_node.val + next_node.val;
                        cost_map[next_node.index] = next_val;
                        next_node.val = next_val;
                        bfs_queue.push(next_node);
                    }
                }
            }
            //while
        }

        int result = 0;
        for (auto&map_item:cost_map)
        {
            result = max(result, map_item.second);
        }

        return result == INT_MAX ? -1 : result;

        //networkDelayTime
    }
private:
    unordered_map<int, vector<Node>>linked_map;
    unordered_map<int, int>cost_map;
};


/*
 一个局域网内有很多台电脑，分别标注为0到N-1的数字。
相连接的电脑距离不一样，所以感染时间不一样，感染时间用t表示。
其中网络内一个电脑被病毒感染，其感染网络内所有的电脑需要最少需要多长时间
如果最后有电脑不会感染，则返回-1。
给定一个数组times表示一个电脑把相邻电脑感染所用的时间。
path[]= {i,j,t} 表示电脑i->j电脑i上的病毒感染j，需要时间t。


输入描述
第一行一个参数，表示局域网内电脑个数N。1<=N<=200
第二行一个参数，表示网络连接条数M
接下来M行，表示网络连接情况，格式为i j t
最后一行一个参数，表示病毒最开始所在的电脑编号


输出描述
一个数字，表示感染电脑所需要花费的所有时间。

输入
4
3
2 1 1
2 3 1
3 4 1
2
输出
2
 */
class Solution02
{
public:
    struct Node
    {
        int index, val;
        Node(int index, int val) :index(index), val(val) {}
        //重载操作符，数值最小的在顶部
        bool operator<(const Node&other)const
        {
            return val > other.val;
        }
    };
    Solution02(vector<vector<int>>&grid, int total, int start)
    {
        //更新linked_map，记录节点关系
        //i j t 表示电脑i->j电脑i上的病毒感染j，需要时间t
        for (auto&linked_v:grid)
        {
            int curr_i = linked_v[0];
            int next_i = linked_v[1];
            int next_val = linked_v[2];

            Node child_node(next_i, next_val);
            linked_map[curr_i].push_back(child_node);
        }
        //建表cost_map
        for (int i=1; i<=total; i++)
        {
            cost_map[i] = INT_MAX;
        }
        //priority_queue 起点入队列
        priority_queue<Node>bfs_queue;
        //起点开销为0
        cost_map[start] = 0;
        bfs_queue.push(Node(start, 0));

        //更新子节点开销
        while (!bfs_queue.empty())
        {
            Node top_node = bfs_queue.top();
            bfs_queue.pop();

            //如果节点值>节点最小，直接跳过，不取这个路径
            if (top_node.val>cost_map.at(top_node.index))
            {
                continue;
            }

            //更新子节点
            if (linked_map.count(top_node.index)>0)
            {
                vector<Node>child_v = linked_map.at(top_node.index);

                for (auto&child_node:child_v)
                {
                    int next_val = top_node.val + child_node.val;
                    if (cost_map.at(child_node.index)==INT_MAX || next_val< cost_map.at(child_node.index))
                    {
                        //符合要求，优于全局最小，更新子节点开销和全局最小开销
                        child_node.val = next_val;
                        cost_map[child_node.index] = next_val;
                        //子节点入队列
                        bfs_queue.push(child_node);
                    }
                }
            }

            //while (!bfs_queue.empty())
        }

        //最终结果为cost_map中的最大值
        int result = 0;
        for (auto&map_item:cost_map)
        {
            result = max(result, map_item.second);
        }

        if (result==INT_MAX)
        {
            cout << -1;
            return;
        }
        cout << result;
        //Solution02
    }
private:
    unordered_map<int, vector<Node>>linked_map;
    unordered_map<int, int>cost_map;
};


/*
 在斗地主扑克牌游戏中，扑克牌由小到大的顺序为：3,4,5,6,7,8,9,10,J,Q,K,A,2。
玩家可以出的扑克牌阵型有：单张、对子顺子、飞机、炸弹等
其中顺子的出牌规则为：由至少5张由小到大连续递增的扑克牌组成，且不能包含2。
例如：{3,4,5,6,7}、{3,4,5,6,7,8,9,10,J,Q,K,A}都是有效的顺子；
而{J,Q,K,A,2}、{2,3,4,5,6}、{3,4,5,6}、{3,4,5,6,8}等都不是顺子。
给定一个包含13张牌的数组，如果有满足出牌规则的顺子，请输出顺子。
如果存在多个顺子，请每行输出一个顺子，且需要按顺子的第一张牌的大小（必须从小到大）依次输出
如果没有满足出牌规则的顺子，请输出No。

输入描述
13张任意顺序的扑克牌，每张扑克牌数字用空格隔开，每张扑克牌的数字都是合法的，并且不包括大小王。比如：
2 9 J 2 3 4 K A 7 9 A 5 6
不需要考虑输入为异常字符的情况

输出描述
组成的顺子，每张扑克牌数字用空格隔开。比如
3 4 5 6 7

输入
2 9 J 2 3 4 K A 7 9 A 5 6
输出
3 4 5 6 7
13张牌中，可以组成的顺子只有1组：3 4 5 6 7

输入
2 9 J 10 3 4 K A 7 Q A 5 6
输出
3 4 5 6 7
9 10 J Q K A

2 9 J 10 3 3 4 4 K A 7 7 Q A 5 5 6 6
 */
class Solution03
{
public:
    static string translateCard(string origin_ch)
    {
        //J 11, Q 12, K 13, A 14, 2 15
        if (origin_ch == "J") return "11";
        if (origin_ch == "11") return "J";

        if (origin_ch == "Q") return "12";
        if (origin_ch == "12") return "Q";

        if (origin_ch == "K") return "13";
        if (origin_ch == "13") return "K";

        if (origin_ch == "A") return "14";
        if (origin_ch == "14") return "A";

        if (origin_ch == "2") return "15";
        if (origin_ch == "15") return "2";

        return origin_ch;
        //translateCard
    }

    static bool Compare(const vector<string>&vec1, const vector<string>&vec2)
    {
        int vec1_0 = stoi(translateCard(vec1[0]));
        int vec2_0 = stoi(translateCard(vec2[0]));

        if (vec1_0==vec2_0)
        {
            return vec1.size() < vec2.size();
        }
        return vec1_0 < vec2_0;
        //compare
    }

    Solution03(vector<string>&str_vec)
    {
        //把牌翻译一下，叠到数组上去
        vector<int>card_vec(16);
        //扫一遍，更新每个牌的数量
        for (auto&str:str_vec)
        {
            string curr_str = translateCard(str);
            int card_index = stoi(curr_str);
            card_vec[card_index] += 1;
        }

        //优先组5个，在5的基础上再顺延
        for (int card_i=3; card_i<15; card_i++)
        {
            while (card_vec[card_i]>0)
            {
                vector<string>track;
                track.push_back(translateCard(to_string(card_i)));

                for (int next=card_i+1; next<=15; next++)
                {
                    if (card_vec[next] == 0)break;
                    if (track.size() == 5) break;

                    track.push_back(translateCard(to_string(next)));
                }

                if (track.size()==5)
                {
                    //更新数量
                    for (auto&str:track)
                    {
                        int index = stoi(translateCard(str));
                        card_vec[index]--;
                    }
                    result.push_back(track);
                }
                else
                {
                    break;
                }
            }
            //for
        }

        //优先组5个，在5的基础上再顺延
        for (auto&min_vec:result)
        {
            string end_card = min_vec[min_vec.size() - 1];
            int end_i = stoi(translateCard(end_card));
            for (int next=end_i+1; next<15; next++)
            {
                if (card_vec[next] == 0)break;
                min_vec.push_back(translateCard(to_string(next)));
                card_vec[next]--;
            }

        }

        if (result.empty())
        {
            cout << "No";
            return;
        }

        //sort(result.begin(), result.end(), Compare);
        sort(result.begin(), result.end(), [](const vector<string>& vec1, const vector<string>& vec2)
        {
				//translateCard改成static就可以过，或者不要放在类里面
                int vec1_0 = stoi(translateCard(vec1[0]));
                int vec2_0 = stoi(translateCard(vec2[0]));

                if (vec1_0 == vec2_0)
                {
                    return vec1.size() < vec2.size();
                }
                return vec1_0 < vec2_0;
        });

        //如果存在多个顺子，请每行输出一个顺子，且需要按顺子的第一张牌的大小（必须从小到大）依次输出
        for (auto&min_vec:result)
        {
	        for (int i=0; i<min_vec.size(); i++)
	        {
                cout << min_vec[i];
                if (i!=min_vec.size()-1)
                {
                    cout << ' ';
                }
	        }
            cout << '\n';
        }

        //Solution03
    }
private:
    vector<vector<string>>result;
};



int main()
{
	{
        vector<string>card_str_v;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;

        while (oh_sstream>>token)
        {
            card_str_v.push_back(token);
        }

        Solution03 solu(card_str_v);

        return 0;
	}
	{
/*
4
3
2 1 1
2 3 1
3 4 1
2

表示局域网内电脑个数N
grid_size
start
*/
        int total, grid_size;
        cin >> total >> grid_size;

        vector<vector<int>>grid(grid_size, vector<int>(3));
        for (int i=0; i<grid_size; i++)
        {
            cin >> grid[i][0] >> grid[i][1] >> grid[i][2];
        }

        int start;
        cin >> start;

        Solution02 solu(grid, total, start);

        return 0;
	}
    //times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
    vector<vector<int>>times = { {2,1,1},{2,3,1},{3,4,1} };
    int n = 4, k = 2;

    Solution01 solu;
    solu.networkDelayTime(times, n, k);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
